//最长递增子序列
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) 
    {
        if(nums.size()<= 1) return nums.size();
        vector<int> dp(nums.size(),1);
        int result = 0;
        for(int i=1;i<nums.size();i++) 
        {
            for (int j = 0; j < i; j++) 
            {
            if(nums[i]>nums[j]) dp[i]=max(dp[i],dp[j]+1);
            }
            if(dp[i]>result) result=dp[i]; // 取长的子序列
        }
        return result;
    }
};
//环绕字符串中唯一的子字符串
class Solution {
public:
    int findSubstringInWraproundString(string s) 
    {
        //dp[i] 以nums[i]结尾的环绕字符串的个数
        int n=s.size();
        vector<int>dp(n,1);
        for(int i=1;i<n;i++)
        {
            if(s[i]-s[i-1]==1 || s[i]=='a' && s[i-1]=='z')
            dp[i]=dp[i-1]+1;
        }
        //需要返回所有的子字符串个数 但是需要去重
        //假定有s中有两个以c结尾的环绕字符串
        //那么必定出现 abc  xyzabc 这样一大一小的情况 
        //发现xyzabc中一定包含了 abc中的所有可能出现的环绕子字符数
        int hash[26]={0};//用哈希表保存以i结尾的子字符串中最大的dp值
        for(int i=0;i<n;i++)
        {
            char ch=s[i];
            if(hash[ch-'a']<dp[i])
            {
                hash[ch-'a']=dp[i];
            }
        }
        int res=0;
        for(auto e:hash) res+=e;
        return res;
    }
};
//摆动序列
class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) 
    {
        if(nums.size()==1) return 1;
        int n=nums.size();
        vector<int>f(n,1),g(n,1);
        //f[i] 以nums[i]结尾的上升的最长的序列
        //g[i] 以nums[i]结尾的下降的最长的序列
        int res=0;
        for(int i=1;i<n;i++)
        {
            for(int j=0;j<i;j++)
            {
                if(nums[j]<nums[i])
                {
                    f[i]=max(g[j]+1,f[i]);
                }
                else if(nums[j] > nums[i])
                {
                    g[i]=max(f[j]+1,g[i]);
                }
            }
            res=max(res,max(f[i],g[i]));
        }
        return res;
    }
};